【题解】【模板】动态DP LCT+DP+矩阵 luoguP4751 | Qiuly's blog!

【题解】【模板】动态DP LCT+DP+矩阵 luoguP4751

Posted on | In | Comments:

看懂了后发现 $\texttt{DDP}$ 其实不难呢……

其实主要思想就是将 $\texttt{DP}$ 转移式搞到矩阵上，然后如果是树形 $\texttt{DP}$ 的话就可以直接上树剖或者是 $LCT$ 进行维护，当然还可以用全局平衡二叉树(不费) 。如果只是线性的话可以直接用线段树等数据结构进行维护了。

注意这道模板树剖的复杂度是 $O(nlog^2n)$ ，而 $LCT$ 的复杂度为 $O(nlogn)$ ，于是窝选择了 $LCT$ ，跑的还挺快。

开始分析题目，如果没有”动态”限制的话就是一个裸的”没有上司的舞会”，解法显然是设 $f[u][0/1]​$ 表示 $u​$ 不选/选 的时候其子树的最大价值，转移显然为：

对于树中的一个节点 $u$ 的所有儿子中有个重儿子，其他的儿子就是轻儿子，我们将重儿子和轻儿子的贡献分开算。设一个 $g[u][0/1]$ ，其值为：

注意上式中的 $v$ 只的是轻儿子，然后 $f$ 的转移就变成了以下形式( $x$ 为重儿子)：

其实这里的 $g$ 很好维护，我们在 $Access$ 的时候只要计算儿子变化时的贡献就好了。

接着我们构造出转移矩阵：

这样子就可以直接更新了，对于每个节点我们只需要维护两个矩阵即可，一个就是上面乘法中的 $g$ 矩阵，一个就是上面乘法中的 $f$ 矩阵。

需要注意的是这是广义矩阵乘法，也就是说这个矩阵乘法的运算规则为：

很像 $floyd$ ，可以直接算了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct matrix {int c[2][2];matrix(){c[0][0]=c[0][1]=c[1][0]=c[1][1]=-inf;}};
matrix operator * (matrix&a,matrix&b) {
    matrix ret;
    for(int i=0;i<2;++i)for(int j=0;j<2;++j)for(int k=0;k<2;++k)
        ret.c[i][j]=max(ret.c[i][j],a.c[i][k]+b.c[k][j]);
    return ret;
}

int v[N],dp[N][2],head[N],nxt[N<<1],to[N<<1],cnt;
void add(int u,int v) {nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt;}

struct link_cut_tree {
    matrix f[N],g[N];
    int ch[N][2],fa[N];
    inline bool isroot(int x) {return !((ch[fa[x]][0]==x)||(ch[fa[x]][1]==x));}
    inline void pushup(int x) {
        f[x]=g[x];
        if(ch[x][0]) f[x]=f[ch[x][0]]*f[x];if(ch[x][1]) f[x]=f[x]*f[ch[x][1]];
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=ch[y][1]==x,v=ch[x][!k];
        if(!isroot(y)) ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;
        if(v) fa[v]=y;fa[y]=x,fa[x]=z;pushup(y);
    } 
    inline void Splay(int x) {
        while(!isroot(x)) {
            if(!isroot(fa[x]))
                rotate((ch[fa[x]][0]==x)^(ch[fa[fa[x]]][0]==fa[x])?x:fa[x]);
            rotate(x);
        }pushup(x);return;
    }
    inline void Access(int x) {
        for(int y=0;x;x=fa[y=x]) {
            Splay(x);
            if(ch[x][1]) {
                g[x].c[0][0]+=max(f[ch[x][1]].c[0][0],f[ch[x][1]].c[1][0]);
                g[x].c[1][0]+=f[ch[x][1]].c[0][0];
            }
            if(y) {
                g[x].c[0][0]-=max(f[y].c[0][0],f[y].c[1][0]);
                g[x].c[1][0]-=f[y].c[0][0];
            }
            g[x].c[0][1]=g[x].c[0][0];
            ch[x][1]=y,pushup(x);
        }return;
    }
    inline void change(int x,int y) {
        Access(x),Splay(x),g[x].c[1][0]-=v[x]-y;
        pushup(x),v[x]=y;return;
    }
    inline void build(int u) {
        dp[u][1]=v[u];
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i];if(v!=fa[u]) {
                fa[v]=u,build(v);
                dp[u][0]+=max(dp[v][0],dp[v][1]);
                dp[u][1]+=dp[v][0];
            }
        }
        g[u].c[0][0]=g[u].c[0][1]=dp[u][0];
        g[u].c[1][0]=dp[u][1];f[u]=g[u];
    }
}T;


int main() {
    int n,m;IN(n),IN(m);
    for(int i=1;i<=n;++i) IN(v[i]);
    for(int i=1,u,v;i<n;++i)IN(u),IN(v),add(u,v),add(v,u);
    T.build(1);
    while(m--) {
        int x,y;IN(x),IN(y);
        T.change(x,y),T.Splay(1);
        printf("%d\n",max(T.f[1].c[0][0],T.f[1].c[1][0]));
    }
    return 0;
}

本文标题:【题解】【模板】动态DP LCT+DP+矩阵 luoguP4751

文章作者:Qiuly

发布时间:2019年04月19日 - 00:00

最后更新:2019年04月19日 - 19:17

原始链接:http://qiulyblog.github.io/2019/04/19/[题解]luoguP4751/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。